package BlockSearch;

public class BlockSearchDemo2 {
    public static void main(String[] args) {

        /*
        分块查找核心思想:
        块内无序,块间有序实现步骤:
        1.创建数组blockArr存放每一个块对象的信息
        2.先查找blockArr确定要查找的数据属于哪一块
        3.再单独遍历这一块数据即可
        */

        int[] arr2 = {27,22,30,40,36,
        13,19,16,20,
        7,10,
        43,50,48};

        //1.要把数据进行分块
        //创建三个块的对象
        Block2 b1 = new Block2(22,40,0,4);
        Block2 b2 = new Block2(13,20,5,8);
        Block2 b3 = new Block2(7,10,9,10);
        Block2 b4 = new Block2(43,50,11,13);

        //定义数组用来管理三个块的对象（索引表)
        Block2[] blockArr = {b1,b2,b3,b4};

        //定义一个变量用来记录要查找的元素
        int num = 48;//13

        //调用方法，传递索引表，数组，要查找的元素
        int index = gexIndex(blockArr,arr2,num);

        //输出
        System.out.println(index);


    }

    //调用方法，传递索引表，数组，要查找的元素
    private static int gexIndex(Block2[] blockArr, int[] arr, int num) {
        //1.确定number是在那一块当中
        int index = findIndexBlock(blockArr,num);
        if(index == -1){
            //表示number不在数组当中
            return -1;
        }

        //2.获取这一块的起始索引和结束索引
        int startIndex = blockArr[index].getStartIndex();
        int endIndex = blockArr[index].getEndIndex();

        //遍历
        for (int i = startIndex; i <= endIndex; i++) {
            if(arr[i] == num){
                return i;
            }
        }

        return -1;
    }

    //定义一个方法，用来确定number在哪一块当中
    public static int findIndexBlock(Block2[] blockArr, int num) {

        //基本查找
        for (int i = 0; i < blockArr.length; i++) {
            if(num <= blockArr[i].getMax() && num >= blockArr[i].getMin()){
                return i;
            }
        }

        return -1;
    }


}

class Block2 {
    private int min;
    private int max;
    private int startIndex;
    private int endIndex;


    public Block2() {
    }

    public Block2(int min, int max, int startIndex, int endIndex) {
        this.min = min;
        this.max = max;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    /**
     * 获取
     * @return min
     */
    public int getMin() {
        return min;
    }

    /**
     * 设置
     * @param min
     */
    public void setMin(int min) {
        this.min = min;
    }

    /**
     * 获取
     * @return max
     */
    public int getMax() {
        return max;
    }

    /**
     * 设置
     * @param max
     */
    public void setMax(int max) {
        this.max = max;
    }

    /**
     * 获取
     * @return startIndex
     */
    public int getStartIndex() {
        return startIndex;
    }

    /**
     * 设置
     * @param startIndex
     */
    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }

    /**
     * 获取
     * @return endIndex
     */
    public int getEndIndex() {
        return endIndex;
    }

    /**
     * 设置
     * @param endIndex
     */
    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }

    public String toString() {
        return "Block2{min = " + min + ", max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
    }
}